#include "heapsort.h"

HeapSort::HeapSort(QObject *parent):
    IAlgo(parent)
{

}

QString HeapSort::name()
{
    return "Heap Sort";
}

void HeapSort::run()
{
    _run_time = 0;
    QVector<int> &data = _data->GetData();
    buildHeap();

    for(int i = data.size() - 1; i >= 0; --i){
        qSwap(data[0], data[i]);
        adjust(1, i - 1);
    }
}

void HeapSort::buildHeap()
{
    QVector<int> &data = _data->GetData();
    for(int i = data.size()/2; i > 0; --i){
        adjust(i, data.size());
    }
}

// last_pos is not included
void HeapSort::adjust(int begin_pos, int last_pos)
{
    QVector<int> &data = _data->GetData();
    int item = data[begin_pos - 1];
    int pos = begin_pos*2;
    while(pos <= last_pos)
    {
        if(pos < last_pos && data[pos] > data[pos - 1]){
            ++pos;
        }
        if(item >= data[pos - 1]){
            break;
        }
        data[pos / 2 - 1] = data[pos - 1];
        pos *= 2;
        ++_run_time;
        _data->Refresh();
    }
    data[pos/2 - 1] = item;
}
